package com.xk._03真题骗._06二叉树;

import com.xk._03真题骗._00bean.TreeNode;

/**
 * @description:
 * @author: xu
 * @date: 2022/11/5 22:00
 */
public class _333最大BST子树 {
    /*
    * 给定一颗二叉树，找到其中最大的二叉搜索树(BST)子树，其中最大指的是
    * 子树节点数最多的。
    * 注：子树必须包含其所有后代
    * */


    /*
    * 作用：返回以root为根节点的二叉树的最大BST子树的节点数
    * 实现：
    *   1. 如果以root为根节点的二叉树S是BST，就返回S的节点数量
    *   2. 否则，就返回largestBSTSubtree(root.left)、largestBSTSubtree(root.right)中的最大值
    * */
    public int largestBSTSubtree(TreeNode root){
        if (root == null) return 0;
        if (isBST(root)) return nodeCount(root);
        return Math.max(largestBSTSubtree(root.left), largestBSTSubtree(root.right));
    }
    private boolean isBST(TreeNode root){

        return false;
    }
    private int nodeCount(TreeNode root){
        return 0;
    }

}
